# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


from typing import List


class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def transfunc(left: int, right: int):
            if left > right:
                return None

            mid = (left + right) // 2

            root = TreeNode(nums[mid])
            root.left = transfunc(left, mid - 1)
            root.right = transfunc(mid + 1, right)

            return root

        return transfunc(0, len(nums) - 1)


if __name__ == "__main__":
    mySol = Solution()
    al = [1, 2, 3, 2, 1, 0, 1]
    bl = [3, 2, 1, 0, 1, 4, 7]
    # al = [0, 0, 0, 0, 1]
    # bl = [1, 0, 0, 0, 0]
    print('feedback:', mySol.findLength3(al, bl))
